package com.lans.binary;

/**
 * @author: lans
 * @date: 2025/2/26
 * @name: 刘宇
 *
 * 抽象类:可以存在非抽象方法
 * 接口:抽象中的抽象 里面都是抽象方法  标准
 *
 */
public class BinaryTree<K extends Comparable<K>,V> {
    //树的根节点
    private Node root;

    //记录树的节点个数
    private int N;

    //插入一个节点
    public void put(K key,V value){
        root  = put(root,key,value);
    }

    //往指定树中插入节点
    public Node put(Node node,K key,V value){
        //判断要插入的节点是否为空
        if(node==null){
            N++;
            return new Node(key,value,null,null);
        }
        //cmp>0 说明传过来的key大于目标节点 放右边
        //cmp<0 说明key小于目标节点 放左边
        //cmp==0 说明找到目标节点 替换原来的值
        int cmp = key.compareTo(node.key);
        if(cmp>0){

            node.right = put(node.right, key, value);

        } else if(cmp<0){

            node.left = put(node.left,key,value);

        }else{
            node.value = value;
        }
        return node;
    }

    //根据key找出对应的value值
    public V get(K key){
        //从根节点开始找
        return get(root,key);
    }

    //从指定的树中找出对应的value值
    public V get(Node node,K key){
        if(node==null ){
            return null;
        }
        int cmp  = key.compareTo(node.key);
        if(cmp>0){

            return get(node.right,key);

        }else if(cmp<0){
            return get(node.left,key);
        }else{
            return node.value;
        }
    }

    //删除value
    public void delete(K key){
        root = delete(root,key);
    }

    // 从指定的树中删除节点
    public Node delete(Node node, K key) {
        if (node == null) {
            return null;
        }
        int cmp = key.compareTo(node.key);
        if (cmp > 0) {
            node.right = delete(node.right, key);
        } else if (cmp < 0) {
            node.left = delete(node.left, key);
        } else {
            N--;
            // node就是要删除的节点
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            }
            // 当前节点左右子树都存在
            // 找到右子树的最小节点
            Node minNode = node.right;
            while (minNode!= null) {
                minNode = minNode.left;
            }

            //删除右子树中的最小结点
            Node temp = node.right;
            while(temp.left!=null){
                if(temp.left.left==null){
                    temp.left = null;
                }else{
                    temp = temp.left;
                }
            }
            // 复制最小节点的值到当前节点
            minNode.left = node.left;
            minNode.right = node.right;
            node = minNode;
        }
        return node;
    }


    //获取树中元素个数
    public int size(){
        return N;
    }
    //查找二叉树中最小的键
    public K getMin(Node node){
        if(node.left!=null){
            return getMin(node.left);
        }else{
            return node.key;
        }
    }

    public K getMin(){
        return getMin(root);
    }

    //查找二叉树中最大节点
    public K getMax(Node node){
        if(node.right!=null){
            return getMax(node.right);
        }else{
            return node.key;
        }
    }
    public K getMax(){
        return getMax(root);
    }

    //设计二叉树节点对象
    private class Node{
        //记录节点key
        private K key;
        //记录节点值value
        private V value;
        //记录左子节点
        private Node left;
        //记录右子节点
        private Node right;

        public Node(K key, V value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        BinaryTree<String,String> binaryTree = new BinaryTree<>();
        binaryTree.put("1","101");
        binaryTree.put("2","102");
        binaryTree.put("3","103");
        binaryTree.put("4","104");
//        binaryTree.delete("3");
//        String s = binaryTree.get("2");
//        System.out.println(s);
//        System.out.println(binaryTree.size());
        System.out.println(binaryTree.getMax());
        System.out.println(binaryTree.getMin());
    }
}